﻿// Bad Cowtractors POJ - 2377.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <algorithm>

using namespace std;
//https://vjudge.csgrandeur.cn/problem/POJ-2377

/*
Bessie 受雇在农场主约翰的 N（2 <= N <= 1,000）个谷仓之间建立一个廉价的互联网络，这些谷仓的编号为 1...N。
农场主约翰已经做了一些调查，发现在成对的谷仓之间有 M（1 <= M <= 20,000）条可能的连接路线。
每条可能的连接路线都有相关的成本 C（1 <= C <= 100,000）。农场主约翰希望花最少的钱来连接网络，他甚至不想付钱给贝西。

贝西意识到约翰农场主不会付钱给她，于是决定做最差的工作。她必须确定一组要安装的连接线，以便：
(i) 这些连接线的总成本尽可能大；
(ii) 所有谷仓都连接在一起（这样就可以通过已安装连接线的路径从任何其他谷仓到达任何谷仓）；
(iii) 连接线之间没有循环（农夫约翰很容易就能发现）。条件（ii）和（iii）确保了最终的连接线看起来像一棵 "树"。

输入
* 第 1 行 两个空格分隔的整数： N 和 M
* 第 2...M+1 行：每行包含三个空格分隔的整数 A、B 和 C，分别描述 A 谷仓和 B 谷仓之间成本为 C 的连接路线。
输出
* 第 1 行： 一个整数，包含连接所有谷仓的最昂贵树的价格。如果无法连接所有谷仓，则输出-1。

样本
5 8
1 2 3
1 3 7
2 3 10
2 4 4
2 5 8
3 4 6
3 5 2
4 5 17


42
提示
最昂贵的树的成本为 17 + 8 + 10 + 7 = 42。它使用以下连接： 4 到 5、2 到 5、2 到 3 和 1 到 3。
*/

const int N = 1010;
const int M = 20010;
struct Edge     // 存储边
{
    int a, b, w;

    bool operator< (const Edge& W)const
    {
        return w > W.w;
    }
}edges[M];
int p[N];
int n, m;

void init() {
    for (int i = 0; i < N; i++) { p[i] = i; }
}

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int solve() {
    sort(edges+1, edges+1 + m);
    init();

    int res = 0; int cnt = 0;
    for (int i = 1; i <= m; i++) {
        int a = edges[i].a; int b = edges[i].b; int w = edges[i].w;

        a = find(a); b = find(b);
        if (a != b) {
            p[a] = b;
            res += w;
            cnt++;
        }
    }

    if (cnt < n - 1) return -1;
    return res;

}


int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> edges[i].a >> edges[i].b >> edges[i].w;
    }

    cout << solve() << endl;

	return 0;
}

